package algorithmExample;

import java.util.Arrays;
import java.util.List;

/**
 * @Author: zhangrongqing
 * @Date: 2019/12/2 10:35
 */
//实现快排，利用分治
public class QuickSortDemo {
    public static void main(String[] args) {
        int arr[] = {3, 7, 2, 9, 1, 4, 6, 8, 10, 5};
        int low = 0;
        int high = arr.length - 1;
        qsort(arr, low, high);
        System.out.println(Arrays.toString(arr));
    }

    /**
     * 将数组拆分，递归进行二分查找
     *
     * @param arr
     * @param low
     * @param high
     */
    private static void qsort(int[] arr, int low, int high) {
        if (low < high) {
            int position = partion(arr, low, high);
            qsort(arr, low, position - 1);
            qsort(arr, position + 1, high);
        }
    }

    /**
     * 按照最右侧的元素为基准，返回基准值在low~high范围中的位置
     *
     * @param arr
     * @param low
     * @param high
     * @return
     */
    private static int partion(int[] arr, int low, int high) {
        int baseVal = arr[high];

        while (low < high) {
            //从左侧开始查找大于基准值的元素，并移到右侧
            while (low < high && arr[low] <= baseVal) {
                low++;
            }
            arr[high] = arr[low];
            //从右侧开始查找小于基准值的元素，并移到左侧
            while (low < high && arr[high] >= baseVal) {
                high--;
            }
            arr[low] = arr[high];
        }
        //将基准值移到中位
        arr[low] = baseVal;
        //返回中间位置
        return low;
    }
}
